#include <iostream>
using namespace std;


// template<typename T>
// void insertion_sort(T arr[], int len){
//     T choose;     // 可以认为是选中，要进行插入的牌
//     int preIndex; // 选中的牌的前一个位置（开始进行插入的）
//     for(int i = 1; i < len; i++){
//         choose = arr[i];
//         preIndex = i-1;
//         while(preIndex >= 0 && arr[preIndex] > choose){
//             // 如果 arr[preIndex] > choose 大于被选中的牌就后移一位
//             arr[preIndex+1] = arr[preIndex];
//             preIndex--;
//         }
//         // 跳出循环说明，已经找到比手牌还小的数, 插入其后面，且下标为preIndex
//         arr[preIndex+1] = choose;
//     }
// }

template<typename T>
void insertion_sort(T arr[], int len){
    T  choose;     // 可以认为是选中，要进行插入的牌
    int preIndex; // 选中的牌的前一个位置（开始进行插入的）----认为前面的牌已经排好序了

    for (int i=1; i<len; i++){
        choose = arr[i];
        for(preIndex = i-1; preIndex >=0 && arr[preIndex] > choose; preIndex -= 1){
            arr[preIndex+1] = arr[preIndex];   // 牌后移
        }
        arr[preIndex+1] = choose;
    }
}

int main() {
        int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        insertion_sort(arr, len);
        for (int i = 0; i < len; i++)
                cout << arr[i] << ' ';
        cout << endl;

        float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
        len = (float) sizeof(arrf) / sizeof(*arrf);
        insertion_sort(arrf, len);
        for (int i = 0; i < len; i++)
                cout << arrf[i] << ' '<<endl;
        return 0;
}
